# 求众数II : https://leetcode-cn.com/problems/majority-element-ii/

class Solution:
    def majorityElement(self, nums: list) -> list:
        """
            利用 摩尔投票思路解决.
            因为超过 n // 3 ，所以最多存在两个这样的元素(候选元素)
            candidate = [元素, 计数]
        """
        x = - 10 ** 9 - 1
        candidate1 = [x, 0]
        candidate2 = [x, 0]

        for num in nums:
            if candidate1[1] > 0 and candidate2[1] > 0:
                if candidate1[0] == num:
                    candidate1[1] += 1
                elif candidate2[0] == num:
                    candidate2[1] += 1
                else:
                    candidate1[1] -= 1
                    candidate2[1] -= 1
            else:
                # 分情况
                # 1. 如果candidate1不为 0
                if candidate1[1] > 0:
                    if candidate1[0] == num:
                        candidate1[1] += 1
                    else: 
                        candidate2[0] = num
                        candidate2[1] += 1    
                # 2. 如果candidate2不为 0
                elif candidate2[1] > 0:
                    if candidate2[0] == num:
                        candidate2[1] += 1
                    else:
                        candidate1[0] = num
                        candidate1[1] += 1
                # 3. 都为0
                else:
                    # 这里还要做 判断主要的原因是， 当 1， 2 都为 0时， 加入当前是 [3, 0], [4, 0] , num = 4 , 如果把 4 赋值给1，就会导致 rst 里有两个 [4, ,4] 重复
                    if candidate1[0] == num:
                        candidate1[0] = num
                        candidate1[1] += 1
                    else:
                        candidate2[0] = num
                        candidate2[1] += 1
        # 最后选出来的元素不一定就是众数，因为没有明确说明， 一定存在众数，要再次进行一下计数
        count1 = 0
        count2 = 0
        rst = []
        n = len(nums)
        for num in nums:
            if num == candidate1[0]:
                count1 += 1
            if num == candidate2[0]:
                count2 += 1        

        if count1 > len(nums) // 3:
            rst.append(candidate1[0])
        if count2 > len(nums) // 3:
            rst.append(candidate2[0])

        # print(candidate1, candidate2)

        return rst


# 优化一下candidate的代码， 这样写是比较简便通用的， 求 n // 4 也可以类似的逻辑写法， 上面写的太乱了
class Solution:
    def majorityElement(self, nums: list) -> list:
        """
            优化逻辑判断
        """
        x = - 10 ** 9 - 1
        candidate1 = [x, 0]
        candidate2 = [x, 0]

        for num in nums:
            if num == candidate1[0]:
                candidate1[1] += 1
            elif num == candidate2[0]:
                candidate2[1] += 1
            elif candidate1[1] == 0:
                candidate1[0] = num
                candidate1[1] += 1
            elif candidate2[1] == 0:
                candidate2[0] = num
                candidate2[1] += 1
            else:
                candidate1[1] -= 1
                candidate2[1] -= 1


nums = [2,1,1,3,1,4,5,6]
nums = [4,1,2,3,4,4,3,2,1,4]


s = Solution()
rst = s.majorityElement(nums)

print(rst)


